#define _CRT_SECURE_NO_WARNINGS 1
//#include<iostream>
//using namespace std;
//#include<stack>
//stack<long long>arr;
//#include<cstring>
//int main()
//{
//	char s[51];
//	cin >> s;
//	int sz = strlen(s);
//	int i = 0;
//	int m = 0;
//	for (i = 0; i < sz-1; i++)
//	{
//		if (s[i] == '+')
//		{
//			long long x = arr.top();
//			arr.pop();
//			long long y = arr.top();
//			arr.pop();
//			arr.push(y + x);
//		}
//		else if (s[i] == '-')
//		{
//			long long x = arr.top();
//			arr.pop();
//			long long y = arr.top();
//			arr.pop();
//			arr.push(y-x);
//		}
//		else if (s[i] == '*')
//		{
//			long long x = arr.top();
//			arr.pop();
//			long long y = arr.top();
//			arr.pop();
//			arr.push(y *x);
//		}
//		else if (s[i] == '/')
//		{
//			long long x = arr.top();
//			arr.pop();
//			long long y = arr.top();
//			arr.pop();
//			arr.push(y / x);
//		}
//		else if (s[i] == '.')
//		{
//			arr.push(m);
//			m = 0;
//		}
//		else
//		{
//			m = m * 10 + s[i] - '0';
//		}
//	}
//	cout << arr.top();
//	return 0;
//}
//#include<iostream>
//using namespace std;
//#include<queue>
//queue<int>s;
//int is_exit(int n,int str[100],int count,int del)
//{
//	int i = 0;
//	for (i = del; i < count; i++)
//	{
//		if (n == str[i])
//		{
//			return 0;
//		}
//	}
//	return 1;
//}
//int main()
//{
//	int m, n;
//	cin >> m >> n;
//	int arr[n];
//
//	int i = 0;
//	int count = 0;
//	int str[n];
//	int del=0;
//	for (i = 0; i < n; i++)
//	{
//		cin >> arr[i];
//	}
//	for (i = 0; i < n; i++)
//	{
//		if (s.empty() != 0)
//		{
//			s.push(arr[i]);
//			str[count] = arr[i];
//			count++;
//		}
//		else if (is_exit(arr[i],str,count,del))
//		{
//			if (s.size() == m)
//			{
//				s.pop();
//				del++;
//			}
//			s.push(arr[i]);
//			str[count] = arr[i];
//			count++;
//		
//		}
//	}
//	cout << count;
//	return 0;
//}
//#include<iostream>
//using namespace std;
//#include<cstring>
//#include<stack>
//#include<cmath>
//stack<long long>arr;
//stack<char>str;
//char s[100010];
//int main()
//{
//	cin >> s;
//	long long sz = strlen(s);
//	long long i = 0;
//	long long a = 0;
//	for (i = 0; i < sz; i++)
//	{
//		if (s[i] >= '0' && s[i] <= '9')
//		{
//			a = a * 10 + s[i]-'0';
//		}
//		if (i == sz-1)
//		{
//			arr.push(a%10000);
//			if (!str.empty())
//			{
//				long long x = arr.top();
//				arr.pop();
//				long long y = arr.top();
//				arr.pop();
//				arr.push(x * y%10000);
//				str.pop();
//			}
//			if (s[i] == '*')
//			{
//				str.push(s[i]);
//			}
//			a = 0;
//		}
//		else if (s[i] == '+'||s[i]=='*')
//		{
//			arr.push(a%10000);
//			if (!str.empty())
//			{
//				long long x = arr.top();
//				arr.pop();
//				long long y = arr.top();
//				arr.pop();
//				arr.push(x * y%10000);
//				str.pop();
//			}
//			if (s[i] == '*')
//			{
//				str.push(s[i]);
//			}
//			a = 0;
//		}
//	}
//	while (arr.size()>1)
//	{
//		long long x = arr.top();
//		arr.pop();
//		long long y = arr.top();
//		arr.pop();
//		arr.push((x + y)%10000);
//	}
//	cout << arr.top();
//	return 0;
//}
//#include<iostream>
//using namespace std;
//#include<stack>
//stack<long long>arr;
//int main()
//{
//	long long a;
//	cin >> a;
//	a %= 10000;
//	arr.push(a);
//	long long b;
//	char s;
//	while (cin >> s >> b)
//	{
//		if (s == '*')
//		{
//			long long tem = arr.top();
//			arr.pop();
//			arr.push(tem * b%10000);
//		}
//		else
//		{
//			arr.push(b);
//		}
//	}
//	while (arr.size()>1)
//	{
//		long long x = arr.top();
//		arr.pop();
//		long long y = arr.top();
//		arr.pop();
//		arr.push((x + y)%10000);
//	}
//	cout << arr.top();
//	return 0;
//}
//#include<iostream>
//#include<stack> 
//using namespace std;
//stack <int> x;
//int a, c;
//char b;
//int main() {
//	cin >> a;
//	a = a % 10000;
//	x.push(a);
//	while (cin >> b >> c) {
//		if (b == '*') {
//			a = x.top();
//			x.pop();
//			x.push(a * c % 10000);
//		}
//		else
//			x.push(c);
//	}
//	a = 0;
//	while (x.size()) {
//		a += x.top();
//		a %= 10000;
//		x.pop();
//	}
//	cout << a << endl;
//	return 0;
//}
//#include<iostream>
//#include<cstdio>
//#include<cmath>
//#include<algorithm>
//#include<sstream>
//#include<cstring>
//#include<string>
//#include<vector>
//#include<map>
//using namespace std;
//
//int main()
//{
//
//	long long ans = 0, temp, num; char op;
//	cin >> temp;
//	while (cin >> op >> num) {
//		if (op == '+') {
//			ans = (ans + temp) % 10000;
//			temp = num;
//		}
//		else {
//			temp = (temp * num) % 10000;
//		}
//	}
//	ans = (ans + temp) % 10000;
//	cout << ans;
//
//	return 0;
//}
//#include<iostream>
//using namespace std;
//#include<queue>
//queue<int>arr;
//int main()
//{
//	int n, m;
//	cin >> n >> m;
//	int i = 0;
//	int count = 1;
//	for (i = 1; i <= n; i++)
//	{
//		arr.push(i);
//	}
//	while (!arr.empty())
//	{
//		if (count < m)
//		{
//			int x = arr.front();
//			arr.pop();
//			arr.push(x);
//			count++;
//		}
//		else 
//		{
//			cout << arr.front() << ' ';
//			arr.pop();
//			count = 1;
//		}
//	}
//	return 0;
//}
